package main

func dp(s string) [][]bool {
	res := make([][]bool, len(s)) // res[i][j] 表示，s[i:j+1] 是否为回文串
	for i := range res {
		res[i] = make([]bool, len(s))
	}

	for i := len(s) - 1; i >= 0; i-- {
		for j := 0; j < len(s); j++ {
			if i >= j {
				res[i][j] = true
			} else {
				// i < j
				res[i][j] = res[i+1][j-1] && s[i] == s[j]
			}
		}
	}

	return res
}

func minCut(s string) int {
	m := dp(s)

	f := make([]int, len(s))
	for i := range s {
		if m[0][i] {
			f[i] = 0
		} else {
			min := len(s)
			for j := 0; j < i; j++ {
				if m[j+1][i] && f[j] < min {
					min = f[j]
				}
			}
			f[i] = min + 1
		}
	}

	return f[len(s)-1]
}
